1. Field of the Invention
The field of the invention is that of the decoding of digital data coded by means of convolutional codes. More specifically, the invention relates to decoding techniques that implement the decision rule based on maximum likelihood and, notably, techniques using a Viterbi algorithm type of decision algorithm.
Convolutional coding is a technique that is much used at present, notably when the data elements are transmitted in the presence of transmission noise, and for example for the transmission of sound digital signals (in DAB: Digital Audio Broadcasting), of images (in EDB or Earth Digital Broadcasting and HDTV or High Definition Television), of data etc.
The general principle of convolutional coding is based on the association, with a source data element, of at least one coded value, obtained by the linear combination of this source data element with at least one of the previous source data elements.
In a standard way, codes such as these are decoded by means of a Viterbi algorithm type of maximum likelihood algorithm. This algorithm gives a binary estimation of each symbol coded at transmission, on the basis of the corresponding symbol received and of a set of previous symbols received. This binary estimation may be weighted if necessary.
The Viterbi algorithm, which shall be described in greater detail hereinafter, is based on the determination of an optimum path in a trellis, by the systematic elimination of a path from among at least two possible paths reaching each node of the trellis. For each node, therefore, there are determined at least two transition metrics representing the distance between the possible transition on each path and the value effectively received by the decoder. These transition metrics enable the computation of the accumulated metrics, representing the noise accumulated on the path considered. An accumulated metric is thus an integral of the transition metrics. According to the Viterbi algorithm, only the path corresponding to the smallest (surviving) accumulated metric is preserved.
The decoding proper consists in making a trace-back, in the trellis, of this optimum path and in setting the value of the samples received as the values corresponding to the end of this optimum path.
The invention relates essentially to the management of the survivor paths and to the trace-back of the optimum path.
2. Description of the Prior Art
Indeed, the implementation of the maximum likelihood algorithms raises numerous problems, notably when it is desired to implant them in integrated components with a view to their industrial-scale exploitation, and especially for operation at high sampling frequencies.
The problem that arises notably is the standard one of the optimization of the two essential characteristics constituted by the useful surface area of the integrated circuit and the computation time.
Two known methods are implemented in the integrated components presently available on the market. These are called the "trace-back" method and the "register exchange" method.
The trace-back method is implemented, for example, in the different circuits SOR 5053, SOR 5073, SOR 5003, . . . manufactured and distributed by the firm SOREP (registered mark).
It implements a standard RAM (random-access memory) for the storage of the path metrics. The writing of the decisions (survivor paths) into the memory and the trace-back of the optimum path have to be done simultaneously.
In a standard way, this trace-back operation consists of the re-reading, one by one, of the decisions stored in the memory, in the direction opposite that in which they were memorized, so as to trace the optimum path back through the diagram of the trellis.
It can clearly be seen that this method cannot be implemented at very high bit rates owing to the large number of successive writing operations and especially reading operations that have to be performed.
This problem is all the more crucial as, of course, the quality of the decoding is a direct function of the number of samples received that are taken into account, i.e. a function of the length of truncation of the decoding.
The second method of "register exchange" enables operation at higher speeds but at the price of far greater complexity, and hence of a far greater surface area of silicon. Hence, the implementation of this method for the SPORT (registered mark) system, produced and distributed by NTT (registered mark) requires two distinct circuits.
This method uses a shift register for each possible state of the coding, said shift register containing all the information on the path leading to this state. Hence, unlike in the previous method, there is no need to carry out a trace-back on the trellis. The decoding information is obtained directly, which naturally makes it possible to achieve higher bit rates.
These different registers are interconnected, in accordance with the trellis corresponding to the chosen code.
For each new metric computed, the registers are interchanged, as a function of the result of the computation and of the trellis, and the oldest symbols of each of the registers are delivered at output.
Each shift register should have a length equal to the memory of the paths, or length of truncation (the length of truncation represents the depth of the trellis from which it is considered that a decision may be taken with adequate safety).
In other words, this method calls for numerous exchanges of data between registers but, by contrast, no trace-back of the trellis, each register containing all the information on the path leading to the corresponding coding state. It is therefore possible to use this method at high frequencies.
However this method is limited, on the technological plane, by the silicon surface area needed. Indeed, while a memory cell (corresponding to a node of the trellis) requires 4 or 5 transistors in a standard static memory (using the trace-back method), it is constituted by a D flip-flop, i.e. it uses about 15 transistors in the case of the register exchange method.
The surface area needed to store data is therefore multiplied approximately by three. Furthermore, it is generally estimated that the interconnections among the register further double this area.
It is an aim of the invention, notably, to overcome these different drawbacks of the prior art.